package codeRandomThoughts.Test42接雨水;


import java.util.Stack;

//单调栈法
//按行计算
public class Solution3 {
    public static int trap(int[] height) {
        int len = height.length;
        //创建一个单调递增栈(从栈顶到栈底) 栈里面放的是下标
        Stack<Integer> s = new Stack<>();
        int sum = 0;//保存接雨水的总值

        //因为第一个柱子不接雨水,所以直接放到栈里
        s.push(0);

        //开始遍历
        for (int i = 1; i < len; i++) {
            while (!s.isEmpty() && (height[i] >= height[s.peek()])) {
                //要放入的元素大于栈顶元素,此时需要出栈,并根据凹槽计算雨水数量
                Integer bottomIndex = s.pop();//得到的是凹槽底部的下标
                if (!s.isEmpty()) {//必须栈里有元素才能得到leftIndex,没有直接不算雨水了
                    Integer leftIndex = s.peek();
                    //求雨水高度
                    int h = Math.min(height[leftIndex], height[i]) - height[bottomIndex];
                    //雨水宽度
                    int w = i - leftIndex - 1;//自己推一下就知道了
                    sum += h * w;
                }
            }
            s.push(i);
        }
        return sum;
    }
}
